package com.leetcode.offer.chapter5;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author Dennis Li
 * @date 2020/7/16 11:17
 */
public class Permutation_38 {

    List<String> list;
    char[] chars;

    public String[] permutation(String s) {
        chars = s.toCharArray();
        list = new ArrayList<>();
        dfs(0);
        return list.toArray(new String[0]);
    }

    public void dfs(int index) {
        if(index == chars.length - 1){
            list.add(String.valueOf(chars));
            return;
        }
        Set<Character> set = new HashSet<>();
        for (int i = index; i < chars.length; i++) {
            // 如果出现重复的，那么直接跳过
            if(set.contains(chars[i])) continue;
            set.add(chars[i]);
            // 这里是特殊的回溯处理
            // 先交换
            /**
             * 两个Swap操作，目的在于改变原来的字符数组
             * 而每次移动的dfs操作都是通过index + 1来完成和实现的
             */
            swap(i, index);
            // 对新的位置执行dfs
            // 要开始固定第i+1位
            // z这里执行的是向下一层的递归
            dfs(index + 1);
            // 再换回来
            swap(i, index);
        }
    }

    private void swap(int a, int b) {
        char temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

}
